package BinarySearch.Medium;

public class LC0074 {
    /**
     * 二分的本质是每次排除一半的元素，以此实现对数级别的搜索效率。对于非严格递增的数组，每次排除一半的做法仍然是正确的，区别只在于：如果mid指向连续
     * 多个相同数字中的一个，并且nums[mid]!=target，那么本次事实上可以排除多余一半的元素。然而，按照标准的二分搜索排除一半的元素，结果也是正确的。
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int width = matrix[0].length;
        int N = matrix.length * width;

        int left = 0, right = N, mid = (left + right) / 2;
        while (left < right) {
            mid = (left + right) / 2;
            int i = mid / width, j = mid % width;
            if (matrix[i][j] == target) return true;
            if (matrix[i][j] > target) right = mid;
            else left = mid + 1;
        }

        return false;
    }

    public static void main(String[] args) {
        LC0074 solver = new LC0074();
        int[][] matrix = new int[][]{
                {1, 3, 5, 7},
                {10, 11, 16, 20},
                {23, 30, 34, 60}
        };
        solver.searchMatrix(matrix, 3);
    }
}
